YES 1.85 H-Termination proof of /home/matraf/haskell/eval_FullyBlown_Fast/empty.hs
H-Termination of the given Haskell-Program with start terms could successfully be proven:



HASKELL
  ↳ CR

mainModule Main
  ((showSigned :: Real a => (a  ->  [Char ->  [Char])  ->  Int  ->  a  ->  [Char ->  [Char]) :: Real a => (a  ->  [Char ->  [Char])  ->  Int  ->  a  ->  [Char ->  [Char])

module Main where
  import qualified Prelude



Case Reductions:
The following Case expression
case compare x y of
 EQ → o
 LT → LT
 GT → GT

is transformed to
primCompAux0 o EQ = o
primCompAux0 o LT = LT
primCompAux0 o GT = GT



↳ HASKELL
  ↳ CR
HASKELL
      ↳ IFR

mainModule Main
  ((showSigned :: Real a => (a  ->  [Char ->  [Char])  ->  Int  ->  a  ->  [Char ->  [Char]) :: Real a => (a  ->  [Char ->  [Char])  ->  Int  ->  a  ->  [Char ->  [Char])

module Main where
  import qualified Prelude



If Reductions:
The following If expression
if primGEqNatS x y then Succ (primDivNatS (primMinusNatS x y) (Succ y)) else Zero

is transformed to
primDivNatS0 x y True = Succ (primDivNatS (primMinusNatS x y) (Succ y))
primDivNatS0 x y False = Zero

The following If expression
if b then (showChar '(') . p . showChar ')' else p

is transformed to
showParen0 p True = (showChar '(') . p . showChar ')'
showParen0 p False = p

The following If expression
if primGEqNatS x y then primModNatS (primMinusNatS x y) (Succ y) else Succ x

is transformed to
primModNatS0 x y True = primModNatS (primMinusNatS x y) (Succ y)
primModNatS0 x y False = Succ x

The following If expression
if x < 0 then showParen (p > 6) ((showChar '-') . showPos (`negate` x)) else showPos x

is transformed to
showSigned0 p showPos x True = showParen (p > 6) ((showChar '-') . showPos (`negate` x))
showSigned0 p showPos x False = showPos x



↳ HASKELL
  ↳ CR
    ↳ HASKELL
      ↳ IFR
HASKELL
          ↳ BR

mainModule Main
  ((showSigned :: Real a => (a  ->  [Char ->  [Char])  ->  Int  ->  a  ->  [Char ->  [Char]) :: Real a => (a  ->  [Char ->  [Char])  ->  Int  ->  a  ->  [Char ->  [Char])

module Main where
  import qualified Prelude



Replaced joker patterns by fresh variables and removed binding patterns.

↳ HASKELL
  ↳ CR
    ↳ HASKELL
      ↳ IFR
        ↳ HASKELL
          ↳ BR
HASKELL
              ↳ COR

mainModule Main
  ((showSigned :: Real a => (a  ->  [Char ->  [Char])  ->  Int  ->  a  ->  [Char ->  [Char]) :: Real a => (a  ->  [Char ->  [Char])  ->  Int  ->  a  ->  [Char ->  [Char])

module Main where
  import qualified Prelude



Cond Reductions:
The following Function with conditions
compare x y
 | x == y
 = EQ
 | x <= y
 = LT
 | otherwise
 = GT

is transformed to
compare x y = compare3 x y

compare0 x y True = GT

compare2 x y True = EQ
compare2 x y False = compare1 x y (x <= y)

compare1 x y True = LT
compare1 x y False = compare0 x y otherwise

compare3 x y = compare2 x y (x == y)

The following Function with conditions
gcd' x 0 = x
gcd' x y = gcd' y (x `rem` y)

is transformed to
gcd' x zx = gcd'2 x zx
gcd' x y = gcd'0 x y

gcd'0 x y = gcd' y (x `rem` y)

gcd'1 True x zx = x
gcd'1 zy zz vuu = gcd'0 zz vuu

gcd'2 x zx = gcd'1 (zx == 0) x zx
gcd'2 vuv vuw = gcd'0 vuv vuw

The following Function with conditions
gcd 0 0 = error []
gcd x y = 
gcd' (abs x) (abs y)
where 
gcd' x 0 = x
gcd' x y = gcd' y (x `rem` y)

is transformed to
gcd vux vuy = gcd3 vux vuy
gcd x y = gcd0 x y

gcd0 x y = 
gcd' (abs x) (abs y)
where 
gcd' x zx = gcd'2 x zx
gcd' x y = gcd'0 x y
gcd'0 x y = gcd' y (x `rem` y)
gcd'1 True x zx = x
gcd'1 zy zz vuu = gcd'0 zz vuu
gcd'2 x zx = gcd'1 (zx == 0) x zx
gcd'2 vuv vuw = gcd'0 vuv vuw

gcd1 True vux vuy = error []
gcd1 vuz vvu vvv = gcd0 vvu vvv

gcd2 True vux vuy = gcd1 (vuy == 0) vux vuy
gcd2 vvw vvx vvy = gcd0 vvx vvy

gcd3 vux vuy = gcd2 (vux == 0) vux vuy
gcd3 vvz vwu = gcd0 vvz vwu

The following Function with conditions
reduce x y
 | y == 0
 = error []
 | otherwise
 = x `quot` d :% (y `quot` d)
where 
d  = gcd x y

is transformed to
reduce x y = reduce2 x y

reduce2 x y = 
reduce1 x y (y == 0)
where 
d  = gcd x y
reduce0 x y True = x `quot` d :% (y `quot` d)
reduce1 x y True = error []
reduce1 x y False = reduce0 x y otherwise

The following Function with conditions
absReal x
 | x >= 0
 = x
 | otherwise
 = `negate` x

is transformed to
absReal x = absReal2 x

absReal0 x True = `negate` x

absReal1 x True = x
absReal1 x False = absReal0 x otherwise

absReal2 x = absReal1 x (x >= 0)

The following Function with conditions
undefined 
 | False
 = undefined

is transformed to
undefined  = undefined1

undefined0 True = undefined

undefined1  = undefined0 False



↳ HASKELL
  ↳ CR
    ↳ HASKELL
      ↳ IFR
        ↳ HASKELL
          ↳ BR
            ↳ HASKELL
              ↳ COR
HASKELL
                  ↳ LetRed

mainModule Main
  ((showSigned :: Real a => (a  ->  [Char ->  [Char])  ->  Int  ->  a  ->  [Char ->  [Char]) :: Real a => (a  ->  [Char ->  [Char])  ->  Int  ->  a  ->  [Char ->  [Char])

module Main where
  import qualified Prelude



Let/Where Reductions:
The bindings of the following Let/Where expression
reduce1 x y (y == 0)
where 
d  = gcd x y
reduce0 x y True = x `quot` d :% (y `quot` d)
reduce1 x y True = error []
reduce1 x y False = reduce0 x y otherwise

are unpacked to the following functions on top level
reduce2Reduce0 vwv vww x y True = x `quot` reduce2D vwv vww :% (y `quot` reduce2D vwv vww)

reduce2D vwv vww = gcd vwv vww

reduce2Reduce1 vwv vww x y True = error []
reduce2Reduce1 vwv vww x y False = reduce2Reduce0 vwv vww x y otherwise

The bindings of the following Let/Where expression
gcd' (abs x) (abs y)
where 
gcd' x zx = gcd'2 x zx
gcd' x y = gcd'0 x y
gcd'0 x y = gcd' y (x `rem` y)
gcd'1 True x zx = x
gcd'1 zy zz vuu = gcd'0 zz vuu
gcd'2 x zx = gcd'1 (zx == 0) x zx
gcd'2 vuv vuw = gcd'0 vuv vuw

are unpacked to the following functions on top level
gcd0Gcd'1 True x zx = x
gcd0Gcd'1 zy zz vuu = gcd0Gcd'0 zz vuu

gcd0Gcd'2 x zx = gcd0Gcd'1 (zx == 0) x zx
gcd0Gcd'2 vuv vuw = gcd0Gcd'0 vuv vuw

gcd0Gcd' x zx = gcd0Gcd'2 x zx
gcd0Gcd' x y = gcd0Gcd'0 x y

gcd0Gcd'0 x y = gcd0Gcd' y (x `rem` y)



↳ HASKELL
  ↳ CR
    ↳ HASKELL
      ↳ IFR
        ↳ HASKELL
          ↳ BR
            ↳ HASKELL
              ↳ COR
                ↳ HASKELL
                  ↳ LetRed
HASKELL
                      ↳ NumRed

mainModule Main
  ((showSigned :: Real a => (a  ->  [Char ->  [Char])  ->  Int  ->  a  ->  [Char ->  [Char]) :: Real a => (a  ->  [Char ->  [Char])  ->  Int  ->  a  ->  [Char ->  [Char])

module Main where
  import qualified Prelude



Num Reduction: All numbers are transformed to thier corresponding representation with Pos, Neg, Succ and Zero.

↳ HASKELL
  ↳ CR
    ↳ HASKELL
      ↳ IFR
        ↳ HASKELL
          ↳ BR
            ↳ HASKELL
              ↳ COR
                ↳ HASKELL
                  ↳ LetRed
                    ↳ HASKELL
                      ↳ NumRed
HASKELL
                          ↳ Narrow

mainModule Main
  (showSigned :: Real a => (a  ->  [Char ->  [Char])  ->  Int  ->  a  ->  [Char ->  [Char])

module Main where
  import qualified Prelude



Haskell To QDPs


↳ HASKELL
  ↳ CR
    ↳ HASKELL
      ↳ IFR
        ↳ HASKELL
          ↳ BR
            ↳ HASKELL
              ↳ COR
                ↳ HASKELL
                  ↳ LetRed
                    ↳ HASKELL
                      ↳ NumRed
                        ↳ HASKELL
                          ↳ Narrow
                            ↳ AND
QDP
                                ↳ QDPSizeChangeProof
                              ↳ QDP

Q DP problem:
The TRS P consists of the following rules:

new_primMulNat(Succ(vwx50000)) → new_primMulNat(vwx50000)

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:



↳ HASKELL
  ↳ CR
    ↳ HASKELL
      ↳ IFR
        ↳ HASKELL
          ↳ BR
            ↳ HASKELL
              ↳ COR
                ↳ HASKELL
                  ↳ LetRed
                    ↳ HASKELL
                      ↳ NumRed
                        ↳ HASKELL
                          ↳ Narrow
                            ↳ AND
                              ↳ QDP
QDP
                                ↳ QDPSizeChangeProof

Q DP problem:
The TRS P consists of the following rules:

new_esEs(Succ(vwx4200), Succ(vwx6900)) → new_esEs(vwx4200, vwx6900)

R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs: